The invention relates to a method for searching objects in a database.
The invention in particular relates to map searching on mobile (navigation) devices. GPS-based mobile navigation systems are nowadays well established, in particular as so called personal navigation devices (PND) or, increasingly, as software navigation applications on mobile telephones, in particular smart phones, as a whole referred to as navigation devices in the following.
Although increasingly networked navigation solutions within the smart-phone segment play a role (so called connected navigation; for example mobile clients for internet-based map services), the majority of navigation solutions are designed to work in an autarkic manner in that they do not require a (permanent or frequent) network connection (so called offline navigation). This is advantageous on the one hand because of the high costs of network connections, on the other hand because network connections are not always available, especially while travelling, due to limited network coverage in (rural) parts of a country or different network setups in different countries.
An autarkic mobile navigation device must contain the entire map material, typically in a highly compressed form on a data storage medium such as a Flash memory card (for example an SD-card) or the like. Within a navigation device, one of the crucial user interaction operations is the input of and search for an arbitrary object in a map, for example a street address or a particular point of interest (POI), e.g. to enable a user to define the destination of a navigation route. Herein, the complexity of the input operation, in particular the number of required key strokes or selections, possible waiting times and the quality of the interactive feedback, determine the usability of the system and the satisfaction of a user.
Conventional navigation devices in general offer two possibilities to find and locate objects in a map.
On the one hand, a user can determine a destination by interactively moving (panning) and zooming a map segment displayed on a mobile navigation device and, thus, arriving at a map region which contains the destination, such that the destination can be determined by choosing (picking) the destination with a pointer (for example a touch-sensitive screen). This process, however, is tedious, and waiting times may occur due to hardware restrictions of the (mobile) navigation device. In addition, such process is often not practical, because a user must beforehand have a rather precise knowledge about where to find a destination geographically in a map—which often is not the case.
Therefore, navigation devices conventionally offer, on the other hand, a text-based search function by which a user can locate an object according to its name (for example, a street name or the name of a point of interest).
On a stationary computer, such as a desktop computer or a server, it in general poses no problem to exhaustively search the entire stored data records of all available map material. Therefore, such search function is supported by many geo-information systems (GIS) and geo-database software products.
Internet-based map services (such as, in these days, Google maps) optimize search functions in terms of user friendliness and, therein, use functions known from internet search engines. They allow a free text search which compares multiple search terms entered by a user to all attributes of all objects in a map. The search results are then sorted and displayed according to their relevance. Such solutions and there fundamental algorithms, however, cannot be applied within conventional mobile navigation devices, because neither the main memory nor the processor of such navigation devices suffices for the execution of such software applications. Furthermore, the memory of such navigation devices does not provide enough memory space to hold the required standardized map formats (not being compressed or being compressed only insignificantly) and to store additional data files being generated during a data base search (for example data base index files) and being required for the execution of the software.
Because of such limitations, conventional mobile navigation devices provide only simple options for a text-based search. The search process, herein, in general requires a hierarchical geographical confinement, during which a user first must select a region (e.g. country and/or city) and finally a street address or a different search term (such as a name of a point of interest). Only after entering the region, a search for possible street addresses or other search terms is carried out, because conventional search algorithms do not, due to the present hardware limitations of common mobile navigation devices, allow a free text search over all regions of the map in the manner of internet-based map services.